iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 3
0
Modern Web

續說 Ruby on Rails系列 第 3

[Day 3] Ruby Memoization

  • 分享至 

  • xImage
  •  

什麼是 Memoization

Memoization 通常翻譯成 記憶化,或是工程師耳熟能詳的快取(Cache)。
來看看 Wiki 怎麼說:

在計算機科學中,記憶化是一種提高程序運行速度的優化技術。通過儲存大計算量函數的返回值,當這個結果再次被需要時將其從緩存提取,而不用再次計算來節省計算時間。 記憶化是一種典型的時間存儲平衡方案。

所以 Memoization 是用來提高運行速度,使用時機是大計算量函數,如果計算量不大,使用 Memoization 就沒什麼意義了。

Memoization 還有個前提:

相同的輸入時,回傳暫存值。

如果你的函數給予相同的input,卻會出現不同的結果,那也不適合用memorization。例如亂數,或需要用到當下時間。

實作 Memoization

範例一:query result cache

在Rails 專案中,可能會看到像這樣的code

class User < ApplicationRecord
  def all_users
    @users ||= User.all
  end
end

因為Query出所有使用者實在很耗資源,所以透過@users 把計算結果 Cache 起來,並使用||= (conditional assignment) 讓第二次呼叫all_users 不用再呼叫DB。

範例二:如果 Memoization 的結果是false or nil

從第一個簡單範例可以了解到 Memoization 的好處,因為 User.all如果都沒有資料,@users會是空 array。
但如果昂貴的計算(ex. 下面的 expensive_calculation) 結果是 nil or false||= 特性會把昂貴的計算再計算一遍,就失去Memoization 的作用了。

def wanna_cache_result
  @result ||= expensive_calculation
end

def expensive_calculation
   ...
end

這時使用||=還不夠,需要用到 #defined? 這個operator。
改寫 wanna_cache_result

def wanna_cache_result
  return @result if defined?(@result)
   @result ||= expensive_calculatio
end

ps. #defined?(attr) 只要參數是沒定義過的,就回傳nil。如果定義過,會回傳參數的種類,像這裏 @result 如果被指定過值

defined?(@undefined_result)
# => nil

defined?(@result)
# => "instance-variable" 

如果不用 #defined?,就多用個實體來存狀態吧

def wanna_cache_result
  return @result if @has_checked
   @has_checked = true
   @result ||= expensive_calculatio
end

範例三:加速費波納西數列 fibonacci

我們公司面試題很喜歡考費波納西數列,通常我們會這樣解

def fibonacci(n)
  if n == 1 || n == 0
    1
  else
    fibonacci(n - 1) + fibonacci(n - 2)
  end
end

但是 fibonacci(n) 被呼叫的次數隨著n的增加會呈現指數級增長
以下紀錄被呼叫次數

def fibonacci(n)
  @times += 1
  if n < 2
    1
  else
    fibonacci(n - 1) + fibonacci(n - 2)
  end
end

def count_fibonacci(n)
  @times = 0
  @cache = {}
  result = fibonacci(n)
  p "參數為#{n}時,被呼叫#{@times}次,結果是#{result}"
  @times = 0
end

count_fibonacci(1) # "參數為1時,被呼叫1次,結果是1"
count_fibonacci(2) # "參數為2時,被呼叫3次,結果是2"
count_fibonacci(3) # "參數為3時,被呼叫5次,結果是3"
count_fibonacci(5) # "參數為5時,被呼叫15次,結果是8"
count_fibonacci(7) # "參數為7時,被呼叫41次,結果是21"
count_fibonacci(10) #"參數為10時,被呼叫177次,結果是89"
count_fibonacci(20) #"參數為20時,被呼叫21891次,結果是10946"

計算第10個數字需要呼叫177次,計算第20個數字暴增到21891次。嚇到吃手手的數字

使用 Memoization 能夠做到大幅減少 fibonacci被呼叫的次數。


def fibonacci(n)
  @times += 1
  if @cache[n]
    @cache[n]
  else
    result =
      if n < 2
        1
      else
        fibonacci(n - 1) + fibonacci(n - 2)
      end
    @cache[n] = result
  end
end

def count_fibonacci(n)
  @times = 0
  @cache = {}
  result = fibonacci(n)
  p "參數為#{n}時,被呼叫#{@times}次,結果是#{result}"
  @times = 0
end

count_fibonacci(1) # "參數為1時,被呼叫1次,結果是1"
count_fibonacci(2) # "參數為2時,被呼叫3次,結果是2"
count_fibonacci(3) # "參數為3時,被呼叫5次,結果是3"
count_fibonacci(5) # "參數為5時,被呼叫9次,結果是8"
count_fibonacci(7) # "參數為7時,被呼叫13次,結果是21"
count_fibonacci(10) # "參數為10時,被呼叫19次,結果是89"
count_fibonacci(20) # "參數為20時,被呼叫39次,結果是10946"

計算第20個數字只要39次,大幅減少呼叫方法的次數

使用benchmark來看執行時間

require 'benchmark'

def fibonacci_with_cache(n)
  if @cache[n]
    @cache[n]
  else
    result =
      if n < 2
        1
      else
        fibonacci_with_cache(n - 1) + fibonacci_with_cache(n - 2)
      end
    @cache[n] = result
  end
end

def fibonacci(n)
  if n < 2
    1
  else
    fibonacci(n - 1) + fibonacci(n - 2)
  end
end

def count_fibonacci_with_cache(n)
  @cache = {}
  fibonacci_with_cache(n)
end

Benchmark.bm do |x|
  x.report('without_cache') do
    fibonacci(10)
    fibonacci(20)
  end
  x.report('with_cache') do
    count_fibonacci_with_cache(10)
    count_fibonacci_with_cache(20)
  end
end

                 user     system      total        real
without_cache  0.000991   0.000002   0.000993 (  0.000991)
with_cache     0.000019   0.000000   0.000019 (  0.000018)

四個數字依序為:

  1. user CPU time
  2. system CPU time
  3. the sum of the user and system CPU times
  4. the elapsed real time.

時間單位為秒

可以看到使用 Memoization 能夠做到大幅減少 fibonacci被呼叫的時間。

該在哪一層做cache?

這裡要討論的是,是否該在最上層方法做cache。我覺得答案沒有一定,還是要看哪裡最吃系統資源,不過通常在相對底層做比較好。

舉例來說,如果今天收益是收入減去成本

# 雖然下次取得收益會很快,但計算收入跟成本又要再重算一次。
def profit
  @profit ||= (revenue - costs)
end

def revenue
  Sales.all.sum(:amount)
end

def costs
  Cost.all.sum(:amount)
end

改在 #revenue 跟 #costs 做cache

# 減法不會耗去太多時間,又可以讓 revenue跟 costs 有cache效果
def profit
  revenue - costs
end

def revenue
  @revenue ||= Sales.all.sum(:amount)
end

def costs
  @costs ||= Cost.all.sum(:amount)
end

Memoization 萬靈丹?

看到這裡或許會想,既然Memoization這麼有效,那我把每個方法都用上它就好啦。可惜理想很豐滿,現實很骨感,如果你這麼做,Garbage Collection無法順利運作,系統可用記憶體越來越少,而越來越慢。
所以用Memozation之前,先找出最需要的地方就可以了。另外cache也是有時效性,還好我們都是cache在實體變數(instance variables),對Rails來說,每次request都是產生不同的實體,通常不會有cache內容過期的問題。但如果有些東西很多request都會用到,就可以考慮存在類別實體變數(class variables),但是資料的正確跟時效性就要考慮。

本集參考資料

  1. https://www.honeybadger.io/blog/ruby-rails-memoization/#authorDetails
  2. https://syndicode.com/blog/memoization-in-ruby/
  3. https://fred-zone.blogspot.com/2017/04/javascript-memorization.html
  4. https://blog.niclin.tw/2019/08/04/ruby-memoization/
  5. https://pjchender.blogspot.com/2017/09/fibonacci-cache-memoization.html

上一篇
[Day 2] Ruby 的 closure 們: Block, Proc, lambda
下一篇
[Day 4] debug 小幫手 - byebug
系列文
續說 Ruby on Rails10
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言